#ifndef RE_H__
#define RE_H__

#include <assert.h>
#include <stdlib.h>
#include <string.h>

struct Matcher
{
	char character;
	struct Matcher* left;
	struct Matcher* right;
};

struct Matcher* matcher(
	char character,
	struct Matcher* left,
	struct Matcher* right)
{
	struct Matcher* r = malloc(sizeof(struct Matcher));
	r->character = character;
	r->left = left;
	r->right = right;
	return r;
}

/*
struct Matcher* allocateMatcher(
	enum MatcherTag tag,
	struct Matcher* left,
	struct Matcher* right)
{
	assert(tag == CHARACTER ? left == NULL && right == NULL : 1);
	assert(tag == CONCATENATION ? left != NULL && right != NULL : 1);
	assert(tag == REPETITION ? left != NULL && right == NULL : 1);
	assert(tag == UNION ? left != NULL && right != NULL : 1);

	struct Matcher* r = malloc(sizeof(struct Matcher));
	r->tag = tag;
	r->character = character;
	r->left = left;
	r->right = right;
	return r;
}
*/

struct Matcher* compile(char* regex)
{
/*
	struct Matcher* concatenation(char* regex)
	{
		return NULL;
	}

	int depth = 0;
	char* p;
	for(p = regex; ; p++) switch(*p)
	{
		case '(': depth++; break;
		case ')':
			depth--;
			if(depth >= 0) break;
		case '\0':
			return concatenation(regex);
		case '|':
			if(depth == 0)
				return allocateMatcher(
					UNION,
					'\0',
					concatenation(regex),
					compile(p + 1));
	}
*/
	assert(0);
	return NULL;
}

char* match(struct Matcher* matcher, char* string)
{
	assert(string != NULL);

	inline char* last(struct Matcher* matcher, char* string)
	{
		if(matcher == NULL) return string;

		if(matcher->character == *string)
		{
			char* l = last(matcher->left,string + 1);
			char* r = last(matcher->right,string + 1);

			return l > r ? l : r;
		}

		return NULL;
	}

	char* l = last(matcher,string);

	if(l == NULL) return NULL;

	char* r = malloc(l - string + 1);
	memcpy(r,string,l - string);
	r[l - string] = '\0';
	return r;
}

#endif

